package 动态规划专项训练.动态规划训练2;

/**437.书籍复印
 * @author zx
 * @create 2022-04-19 12:38
 */
public class LintCode437 {
    public int copyBooks(int[] pages, int k) {
        int n = pages.length;
        if(n == 0){
            return 0;
        }
        if(k > n){
            k = n;
        }
        int[][] f = new int[k + 1][n + 1];
        int i,j,t;
        f[0][0] = 0;
        //初始化0个人抄书的时间,第1本书 ~ 第n本书
        for(j = 1;j <= n;j++){
            f[0][j] = Integer.MAX_VALUE;
        }
        int sum = 0;
        for(t = 1;t <= k;t++){
            f[t][0] = 0;
            for(i = 1;i <= n;i++){
                f[t][i] = Integer.MAX_VALUE;
                sum = 0;
                for(j = i;j >= 0;j--){
                    f[t][i] = Math.min(f[t][i],Math.max(f[t - 1][j],sum));
                    if(j > 0){
                        sum += pages[j - 1];
                    }
                }
            }
        }
        return f[k][n];
    }
}
